package com.mdnote.practice.disjointed_set;

import javafx.util.BuilderFactory;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/24
 * @description
 */
public class LeetCode130 {

    private int[] dx = {0, -1, 0, 1};
    private int[] dy = {-1, 0, 1, 0};

    public static void main(String[] args) {
        LeetCode130 leetCode130 = new LeetCode130();
//        char[][] board = {
//                {'O','O','O','O','X','X'},
//                {'O','O','O','O','O','O'},
//                {'O','X','O','X','O','O'},
//                {'O','X','O','O','X','O'},
//                {'O','X','O','X','O','O'},
//                {'O','X','O','O','O','O'}
//        };
//        char[][] board = {
//            {'O','X','X','O','X'},
//            {'X','O','O','O','X'},
//            {'X','O','X','O','X'},
//            {'X','O','O','O','X'},
//            {'X','X','X','X','X'},
//        };
        char[][] board = {
                {'O','O','O'},
                {'O','O','O'},
                {'O','O','O'},
        };
        leetCode130.solve(board);

        for (char[] chars : board) {
            System.out.println(Arrays.toString(chars));
        }
    }
    /**
     * 图上的O右两种，一种是和边边有连接的，一种是和边边没连接的
     * @param board
     */
    public void solve(char[][] board) {

        if (board.length == 0) {
            return;
        }
        // dfs
//        dfs(board);

        // disjoint set
        disjoint(board);
    }

    private void disjoint(char[][] board) {

        int m = board.length;
        int n = board[0].length;
        int[] parent = new int[m * n + 1];
        int dummy_parent = m * n;

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }

        // 遍历出所有的O节点
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O') {
                    // 看看是不是边边
                    if (i == 0 || i == board.length - 1 || j == 0 || j == board[0].length - 1) {
                        union(i * board[0].length + j, dummy_parent, parent);
                    } else {
                        for (int k = 0; k < dx.length; k++) {
//                            if (!(i + dx[k] == 0 || i + dx[k] == board.length - 1 || j + dy[k] == 0 || j + dy[k] == board[0].length - 1)) {
//
//                            }
                            if (board[i + dx[k]][j + dy[k]] == 'O') {
                                union(i * board[0].length + j,(i + dx[k]) * board[0].length + (j + dy[k]), parent);
                            }
                        }
                    }
                }
            }
        }

        // 遍历board 看看他们的根节点时谁
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (!isConnected(i * board[0].length + j, dummy_parent, parent)) {
                    board[i][j] = 'X';
                } else {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private boolean isConnected(int x, int y, int[] parent) {
        return find_parent(x, parent) == find_parent(y, parent);
    }


    private int find_parent(int x, int[] parent) {
        while (x != parent[x]) {
//            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    private int union(int x, int y, int[] parent) {
        int x_root = find_parent(x, parent);
        int y_root = find_parent(y, parent);

        if (x_root == y_root) {
            return -1;
        } else {
            parent[x_root] = y_root;
        }
        return 0;
    }

    private void dfs(char[][] board) {

        // 找边边为O的
        for (int i = 0; i < board.length; i++) {
            _dfs(i, 0, board);
            _dfs(i, board[0].length - 1, board);
        }
        for (int i = 0; i < board[0].length; i++) {
            _dfs(0, i, board);
            _dfs(board.length - 1, i, board);
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void _dfs(int row, int column, char[][] board) {
        // Terminator
        if (row < 0  || row >= board.length  || column < 0 || column >= board[0].length || board[row][column] != 'O' ) {
            return;
        }
        // Process current logic
        board[row][column] = 'A';
        for (int i = 0; i < dx.length; i++) {
            _dfs(row + dx[i], column + dy[i], board);
        }
    }
}




